package com.example.demo.algorithms;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;


/**
 * <p>Description: 归并排序</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/3/6 15:21
 **/

public class MergerSort {

    public static void main(String[] args) {
        int[] array = {12, 10, 9, 8};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }


    private static void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;


        mergeSort(array, start, mid);

        mergeSort(array, mid + 1, end);

        merge(array, start, mid, end);
        List<Integer> arrayList = Arrays.stream(array).boxed().collect(Collectors.toList());
        System.out.print("合并后左：" + arrayList.subList(start, mid).toString());
        System.out.println("合并后右：" + arrayList.subList(mid + 1, end).toString());
    }

    // 将两个有序序列归并为一个有序序列(二路归并)

    /**
     * 归并排序算法
     *
     * @param array 数组
     * @param start 左边下标
     * @param mid   中间下标
     * @param end   右边下标
     */
    private static void merge(int[] array, int start, int mid, int end) {

        int[] result = new int[end + 1]; // 定义一个临时数组，用来存储排序后的结果
        int current = start; // 临时数组的索引
        int initStart = start;

        int midNext = mid + 1;
        // 取出最小值放入临时数组中
        while (start <= mid && midNext <= end) {
            if (array[start] > array[midNext]) {
                result[current++] = array[midNext++];
            } else {
                result[current++] = array[start++];
            }
        }

        // 若还有段序列不为空，则将其加入临时数组末尾
        while (start <= mid) {
            result[current++] = array[start++];
        }
        while (midNext <= end) {
            result[current++] = array[midNext++];
        }

        // 将临时数组中的值copy到原数组中
        for (int i = initStart; i <= end; i++) {
            array[i] = result[i];
        }

    }


}
